package org.design.strategyPattern;

import java.util.List;

/**
 * 快速排序算法实现类 - 策略模式中的具体策略
 * <p>
 * 在策略模式中的角色：
 * 1. 这是具体策略类，实现了AlgorithmStrategy接口
 * 2. 提供了快速排序算法的具体实现
 * 3. 可以通过AlgorithmContext在运行时动态切换使用
 * <p>
 * 算法特点：
 * 1. 平均时间复杂度：O(nlogn)
 * 2. 最坏时间复杂度：O(n²)，发生在输入数组已经有序或逆序的情况
 * 3. 空间复杂度：O(logn)，主要是递归调用栈的开销
 * 4. 不稳定排序：相同值的元素在排序后可能会改变相对位置
 * <p>
 * 优化策略：
 * 1. 使用随机选择基准值来避免最坏情况
 * 2. 对小规模子数组可以使用插入排序来提高效率
 *
 * @author 樊温军
 * @date 2025/6/24 上午10:39
 */
public class QuickSortAlgorithm implements AlgorithmStrategy {

    /**
     * 排序方法的公共接口实现
     * 调用私有的quickSort方法进行实际排序
     *
     * @param arr 需要排序的整数列表
     */
    @Override
    public void sort(List<Integer> arr) {
        int n = arr.size();
        quickSort(arr, 0, n - 1);
    }

    /**
     * 快速排序的递归实现
     *
     * @param arr 需要排序的整数列表
     * @param l   当前处理区间的左边界
     * @param r   当前处理区间的右边界
     */
    private void quickSort(List<Integer> arr, int l, int r) {
        // 基本情况：如果左边界大于等于右边界，说明区间只有0或1个元素，已经有序
        if (l >= r) {
            return;
        }
        // 对当前区间进行分区，返回分区点的索引
        int p = partition(arr, l, r);
        // 递归地对分区点左侧的子数组进行排序
        quickSort(arr, l, p - 1);
        // 递归地对分区点右侧的子数组进行排序
        quickSort(arr, p + 1, r);
    }

    /**
     * 分区函数，将数组分为两部分：小于基准值的部分和大于基准值的部分
     *
     * @param arr 需要分区的整数列表
     * @param l   当前处理区间的左边界
     * @param r   当前处理区间的右边界
     * @return 分区点的索引，使得该点左侧的元素都小于该点的元素，右侧的元素都大于该点的元素
     */
    private int partition(List<Integer> arr, int l, int r) {
        // 随机在arr[l...r]的范围中选择一个数值作为基准点pivot
        // 这样做可以避免在已经有序的数组上出现最坏情况
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
        // 取第一个元素（已经是随机选择的）作为基准值
        Integer v = arr.get(l);
        // 维护两个区间：
        // arr[l+1...j] < v （小于基准值的区间）
        // arr[j+1...i) > v （大于基准值的区间）
        int j = l;
        // 遍历数组中的每个元素
        for (int i = l + 1; i <= r; i++) {
            // 如果当前元素小于基准值
            if (arr.get(i) < v) {
                // 扩展小于基准值的区间
                j++;
                // 将当前元素交换到小于基准值的区间
                swap(arr, j, i);
            }
            // 如果当前元素大于等于基准值，不需要操作，i自增会自动扩展大于基准值的区间
        }
        // 最后将基准值放到正确的位置（小于区间的末尾）
        swap(arr, l, j);
        // 返回基准值的最终位置
        return j;
    }

}
